package com.linchong.dynamicprogramming.medium;

/**
 * @author linchong
 * @version 1.0
 * @Date: 2020-11-20 11:34
 * @Description: LongestIncreasingSubsequence$300-最长上升子序列-https://leetcode-cn.com/problems/longest-increasing-subsequence/
 */
public class LongestIncreasingSubsequence {

	/**
	 *
	 * 给定一个无序的整数数组，找到其中最长上升子序列的长度。
	 *
	 * 示例:
	 *
	 * 输入: [10,9,2,5,3,7,101,18]
	 * 输出: 4
	 * 解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
	 * 说明:
	 *
	 * 可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
	 * 你算法的时间复杂度应该为 O(n2) 。
	 * 进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?
	 *
	 * 来源：力扣（LeetCode）
	 * 链接：https://leetcode-cn.com/problems/longest-increasing-subsequence
	 *
	 * step1 确定状态
	 *      最后一步：
	 *          对于最优的策略，一定有最后一个元素a[j]
	 *              第一种情况：最优策略中最长上升子序列就是{a[j]},答案为1
	 *              第二种情况：子序列长度大于1，则最优策略中a[j]的前一个元素是a[i],并且a[i]<a[j]
	 *              因为是最优策略，则它选中的以a[i]结尾的上升子序列一定是最长的
	 *      子问题：
	 *          因为不确定最优策略中a[j]的前一个元素a[i]是那一个，所以需要枚举每个i
	 *
	 *      原本求以a[j]结尾的最长上升子序列 转化为求 以a[i]结尾的最长上升子序列
	 *      转化子问题i<j
	 *
	 *      状态：设f[j]=以a[j]结尾的最长上升子序列的长度
	 * step2 转移方程
	 *      设f[j]=以a[j]结尾的最长上升子序列的长度
	 *              f[j] = max{1,f[i]+1|i<j && a[i]<a[j]}
	 *              子序列就是a[j]本身             以a[i]结尾的最长上升子序列的长度，加上a[j]
	 *
	 *
	 * step3 边界值和初始化条件
	 *       初始条件空
	 *       情况2：
	 *          i>=0
	 *          a[j]>a[i],满足单调性1
	 *
	 * step4 计算顺序
	 *      f[0],f[1],...,f[n-1]
	 *
	 *  结果：max{f[0],f[1],...,f[n-1]}
	 *
	 *  时间复杂度：O(n^2),空间复杂度：O(n)
	 *
	 *  todo: nlogn时间复杂度
	 *
	 */

	public int lengthOfLIS(int[] nums) {

		int n = nums.length;
		if(n==0){
			return 0;
		}

		int[] f = new int[n];
		int res = 0;

		for (int i = 0; i < n; i++) {
			f[i] = 1;
			for (int j = 0; j < i; j++) {
				if(nums[j]<nums[i] && f[j]+1>f[i]){
					f[i] = f[i]+1;
				}
			}
			res = Math.max(res,f[i]);
		}

		return res;
	}
	public static void main(String[] args) {

		int[] nums = {10,9,2,5,3,7,101,18};
		LongestIncreasingSubsequence instance = new LongestIncreasingSubsequence();
		System.out.println(instance.lengthOfLIS(nums));
	}
}
